package offer;
//二叉搜索树与双向链表
public class T27 {

     public class TreeNode {
     int val = 0;
     TreeNode left = null;
     TreeNode right = null;

     public TreeNode(int val) {
     this.val = val;

     }

     }

        public TreeNode Convert(TreeNode pRootOfTree) {
           if (pRootOfTree==null) return pRootOfTree;
            pRootOfTree = getlist(pRootOfTree).right;
            pRootOfTree.left.right=null;
            pRootOfTree.left=null;
            return pRootOfTree;
        }
        public TreeNode getlist(TreeNode pRootOfTree) {
            if (pRootOfTree==null) return null;
            TreeNode left = pRootOfTree.left;
            TreeNode right = pRootOfTree.right;
            pRootOfTree.left=pRootOfTree;
            pRootOfTree.right=pRootOfTree;
            if (left!=null) {
                TreeNode leftTree = getlist(left);
                TreeNode frist = leftTree.right;
                leftTree.right=pRootOfTree;
                pRootOfTree.left=leftTree;
                pRootOfTree.right=frist;
                frist.left=pRootOfTree;
            }
            if (right!=null) {
                TreeNode rightTree = getlist(right);
                TreeNode frist = rightTree.right;
                TreeNode sta = pRootOfTree.right;
                pRootOfTree.right=frist;
                frist.left=pRootOfTree;
                rightTree.right=sta;
                sta.left = rightTree;
                pRootOfTree = rightTree;
            }
           // print(pRootOfTree,pRootOfTree.right);
            //System.out.println("\n------------------------");
            return pRootOfTree;

        }
    /* 中序遍历
    private TreeNode root;
    private TreeNode last;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree==null) return null;
        mmp(pRootOfTree);
        return root;
    }
    public void mmp(TreeNode pRootOfTree) {
        if (pRootOfTree==null) return ;
        mmp(pRootOfTree.left);
        if (root==null) {
            root = pRootOfTree;
            last = pRootOfTree;
        } else {
            last.right = pRootOfTree;
            pRootOfTree.left = last;
            last = pRootOfTree;
        }
        mmp(pRootOfTree.right);
    }
    */
    public void test() {
        TreeNode treeNode1 = new TreeNode(10);
        TreeNode treeNode2 = new TreeNode(6);
        TreeNode treeNode3 = new TreeNode(14);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(8);
        TreeNode treeNode6 = new TreeNode(12);
        TreeNode treeNode7 = new TreeNode(16);
        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right=treeNode5;
        treeNode3.left=treeNode6;
        treeNode3.right=treeNode7;
        TreeNode root =Convert(treeNode1);
        print(root,null);
    }
    public void print(TreeNode root,TreeNode end) {
         if (root==end) {
             if (root!=null)
             System.out.print(root.val+" ");
             return;
         }
         System.out.print(root.val+" ");
         print(root.left,end);
        // print(root.right,end);
    }
        public static void main ( String[] args) {
            new T27().test();

        }
}
